import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

/**
 * 颜色分类
 */
public class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        int left = -1, right = len, cur = 0, tmp = 0;
        while(cur < right) {
            if (nums[cur] == 0) {
                left++;
                tmp = nums[cur];
                nums[cur] = nums[left];
                nums[left] = tmp;
                if (cur <= left) {
                    cur++;
                }
            } else if (nums[cur] == 2) {
                right--;
                tmp = nums[cur];
                nums[cur] = nums[right];
                nums[right] = tmp;
            } else {
                cur++;
            }
        }
    }

    /**
     * 排序数组（分治 归并）
     * @param nums
     * @return
     */
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
    public void mergeSort(int[] nums, int left, int right) {
        // 递归出口
        if (right <= left) {
            return;
        }
        // 随机生成基准元素
        Random random = new Random();
        int key = nums[random.nextInt(right - left + 1) + left];
        // 将数字划分为三块 < key、= key 和 > key
        int l = left - 1, r = right + 1, cur = left;
        while(cur < r) {
            if (nums[cur] < key) {
                swap(nums, ++l, cur++);
            } else if (nums[cur] == key) {
                cur++;
            } else {
                swap(nums, --r, cur);
            }
        }
        // 继续递归
        mergeSort(nums, left, l);
        mergeSort(nums, r, right);
    }

    /**
     * 数组中第 K 个最大元素
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        return qSort(nums, 0, nums.length - 1, k);
    }

    public int qSort(int[] nums, int left, int right, int k) {
        if (right <= left) {
            return nums[left];
        }
        // 随机生成基准元素
        Random random = new Random();
        int key = nums[random.nextInt(right - left + 1) + left];
        // 将数字划分为三块 < key、= key 和 > key
        int l = left - 1, r = right + 1, cur = left;
        while(cur < r) {
            if (nums[cur] < key) {
                swap(nums, ++l, cur++);
            } else if (nums[cur] == key) {
                cur++;
            } else {
                swap(nums, --r, cur);
            }
        }
        // 判断是否找到第 k 个最大元素
        if (right - r + 1 >= k) {
            // 未找到，继续递归
            return qSort(nums, r, right, k);
        } else if (right - l >= k) {
            // 找到了，直接返回
            return key;
        } else {
            // 未找到，继续递归
            return qSort(nums, left, l, k - (right - l));
        }
    }

    /**
     * 最小的 k 个数
     * @param arr
     * @param k
     * @return
     */
    public int[] smallestK(int[] arr, int k) {
        int[] res = new int[k];
        qSort2(arr, 0, arr.length - 1, k);
        for(int i = 0; i < k; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public void qSort2(int[] nums, int left, int right, int k) {
        if (right <= left) {
            return;
        }
        // 随机生成基准元素
        Random random = new Random();
        int key = nums[random.nextInt(right - left + 1) + left];
        // 将数字划分为三块 < key、= key 和 > key
        int l = left - 1, r = right + 1, cur = left;
        while(cur < r) {
            if (nums[cur] < key) {
                swap(nums, ++l, cur++);
            } else if (nums[cur] == key) {
                cur++;
            } else {
                swap(nums, --r, cur);
            }
        }
        // 判断
        if (l - left + 1 > k) {
            qSort2(nums, left, l, k);
        } else if (r - left >= k){
            return;
        } else {
            qSort2(nums, r, right, k - (r - left));
        }
    }

    /**
     * 排序数组——归并
     * @param nums
     * @return
     */
    public int[] sortArray2(int[] nums) {
        mergerSort2(nums, 0, nums.length - 1);
        return nums;
    }
    public void mergerSort2(int[] nums, int left, int right) {
        // 递归出口
        if (right <= left) {
            return;
        }
        int mid = (left + right) / 2;
        // 继续递归
        mergerSort2(nums, left, mid);
        mergerSort2(nums, mid + 1, right);
        // 合并
        int[] tmp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while(i <= mid && j <= right) {
            if (nums[i] < nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        while(i <= mid) {
            tmp[k++] = nums[i++];
        }
        while(j <= right) {
            tmp[k++] = nums[j++];
        }
        for(i = 0; i < tmp.length; i++) {
            nums[left + i] = tmp[i];
        }
    }

    /**
     * 数组中的逆序对
     * @param record
     * @return
     */
    public int reversePairs(int[] record) {
        return findReversePairs(record, 0, record.length - 1);
    }
    public int findReversePairs(int[] nums, int left, int right) {
        // 递归出口
        if (right <= left) {
            return 0;
        }
        // 查找左右两边的逆序对
        int mid = (left + right) / 2;
        int lrecord = findReversePairs(nums, left, mid);
        int rrecord = findReversePairs(nums, mid + 1, right);
        // 合并之后总的逆序对
        int i = left, j = mid + 1, count = 0;
        while(i <= mid && j <= right) {
            if (nums[i] > nums[j]) {
                count += (right - j + 1);
                i++;
            } else {
                j++;
            }
        }

        // 合并排序(逆序)
        int[] tmp = new int[right - left + 1];
        int k = 0;
        i = left;
        j = mid + 1;
        while(i <= mid && j <= right) {
            if (nums[i] > nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        while(i <= mid) {
            tmp[k++] = nums[i++];
        }
        while(j <= right) {
            tmp[k++] = nums[j++];
        }
        for(i = 0; i < tmp.length; i++) {
            nums[left + i] = tmp[i];
        }

        return (count + lrecord + rrecord);
    }


    /**
     * 计算右侧小于当前元素的个数
     * @param nums
     * @return
     */
    public List<Integer> countSmaller(int[] nums) {
        int len = nums.length;
        int[] index = new int[len]; // 记录下标对应位置
        int[] count = new int[len];
        for(int i = 0; i < len; i++) {
            index[i] = i;
        }
        // 查找
        mergerSort(nums, 0, len - 1, index, count);
        // int 类型不能直接转化
        return Arrays.stream(count).boxed().collect(Collectors.toList());
    }
    public void mergerSort(int[] nums, int left, int right, int[] index, int[] count) {
        // 递归出口
        if (right <= left) {
            return;
        }
        // 查找左右两边的逆序对
        int mid = (left + right) / 2;
        mergerSort(nums, left, mid, index, count);
        mergerSort(nums, mid + 1, right, index, count);
        // 合并之后的逆序对
        int i = left, j = mid + 1;
        while(i <= mid && j <= right) {
            if (nums[i] > nums[j]) {
                count[index[i]] += (right - j + 1);
                i++;
            } else {
                j++;
            }
        }

        // 合并排序(逆序)
        // 在合并过程中调整对应 index 位置
        int[] tmp = new int[right - left + 1];
        int[] tmpIndex = new int[right - left + 1];
        int k = 0;
        i = left;
        j = mid + 1;
        while(i <= mid && j <= right) {
            if (nums[i] > nums[j]) {
                tmpIndex[k] = index[i];
                tmp[k++] = nums[i++];
            } else {
                tmpIndex[k] = index[j];
                tmp[k++] = nums[j++];
            }
        }
        while(i <= mid) {
            tmpIndex[k] = index[i];
            tmp[k++] = nums[i++];
        }
        while(j <= right) {
            tmpIndex[k] = index[j];
            tmp[k++] = nums[j++];
        }
        for(i = 0; i < tmp.length; i++) {
            nums[left + i] = tmp[i];
            index[left + i] = tmpIndex[i];
        }
    }

    /**
     * 翻转对
     * @param nums
     * @return
     */
    public int reversePairs2(int[] nums) {
        return findReversePairs2(nums, 0, nums.length - 1);
    }
    public int findReversePairs2(int[] nums, int left, int right) {
        // 递归出口
        if (right <= left) {
            return 0;
        }
        // 继续递归
        int mid = (left + right) / 2;
        int lcount = findReversePairs2(nums, left, mid);
        int rcount = findReversePairs2(nums, mid + 1, right);
        // 合并寻找翻转对
        int i = left, j = mid + 1, count = 0;
        while (i <= mid && j <= right) {
            if (nums[i] / 2.0 > nums[j]) {
                count += (right - j + 1);
                i++;
            } else {
                j++;
            }
        }
        // 合并(逆序)
        int[] tmp = new int[right - left + 1];
        int k = 0;
        i = left;
        j = mid + 1;
        while(i <= mid && j <= right) {
            if (nums[i] > nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        while(i <= mid) {
            tmp[k++] = nums[i++];
        }
        while(j <= right) {
            tmp[k++] = nums[j++];
        }
        for(i = 0; i < tmp.length; i++) {
            nums[left + i] = tmp[i];
        }
        return (count + lcount + rcount);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {0,2,1};
        solution.countSmaller(nums);
    }
}
